package std::collection;

import std::Object;

public class LinkedList : List 
{
	private m_head->LinkedListNode;
	private m_tail->LinkedListNode;
	private m_size->int;

	public LinkedList()
	{
		m_head=new LinkedListNode();
		m_tail=m_head;
		m_size=0;
	}

	public add(e->Object)
	{
		if(e==null)return;
		node->LinkedListNode=new LinkedListNode();
		node.data=e;
		m_tail.next=node;
		m_tail=node;
		++m_size;
	}

	public remove(index->int)
	{
		if(0<=index && index<m_size){
			i->int=0;
			node->LinkedListNode=m_head;
			while(node.next!=null){
				if(i==index){
					node.next=node.next.next;
					--m_size;
					if(node.next==null){
						m_tail=node;
					}
					return;
				}
				node=node.next;
				++i;
			}
		}
	}

	public remove(e->Object)
	{
		if(e==null)return;
		node->LinkedListNode=m_head;
		while(node.next!=null){
			if(node.next.data.equals(e)){
				node.next=node.next.next;
				--m_size;
				if(node.next==null){
					m_tail=node;
				}
				return;
			}
			node=node.next;
		}
	}

	public get(index->int)->Object 
	{
		if(0<=index && index<m_size){
			i->int=0;
			node->LinkedListNode=m_head;
			while(node.next !=null){
				if(i==index){
					return node.next.data;
				}
				node=node.next;
				++i;
			}
		}
		return null;
	}

	public set(index->int, e->Object)
	{
		if(e==null)return;
		if(0<=index&&index<m_size){
			node->LinkedListNode=m_head;
			i->int=0;
			while(i<m_size){
				if(i==index){
					node.next.data=e;
					return;
				}
				++i;
				node=node.next;
			}
		}
	}

	public index(e->Object)->int
	{
		if(e==null)return -1;
		i->int=0;
		node->LinkedListNode=m_head;
		while(node.next!=null){
			if(node.next.data.equals(e)){
				return i;
			}
			++i;
			node=node.next;
		}
		return -1;
	}

	public exist(e->Object)->boolean
	{
		if(e==null)return false;
		node->LinkedListNode=m_head;
		while(node.next!=null){
			if(node.next.data.equals(e)){
				return true;
			}
			node=node.next;
		}
		return false;
	}

	public empty()->boolean{return m_size==0;}

	public clear()
	{
		m_head.next=null;
		m_tail=m_head;
		m_size=0;
	}

	public size()->int{return m_size;}
	public iterator()->Iterator{return new LinkedListIterator(m_head.next);}

	public toArray()->Object[]
	{
		if(empty())return null;
		temp->Object[]=new Object[m_size];
		i->int=0;
		node->LinkedListNode=m_head.next;
		while(node!=null){
			temp[i]=node.data;
			node=node.next;
			++i;
		}
		return temp;
	}
}


class LinkedListNode : Object
{
	public next->LinkedListNode=null;
	public data->Object=null;
	public LinkedListNode(){}
}

class LinkedListIterator : Iterator
{
	private m_index->LinkedListNode;
	public LinkedListIterator(node->LinkedListNode){m_index=node;}
	public hasNext()->boolean{return m_index!=null;}
	public next()->Object
	{
		if(m_index==null)return null;
		else {
			item->Object=m_index.data;
			m_index=m_index.next;
			return item;
		}
	}
}